// 1922. 统计好数字的数目
// AC:https://leetcode.cn/problems/count-good-numbers/submissions/621716453/

class Solution {
public:
    static const int m=1e9+7;
    int fastpow(int a,long long n){
        int base=a,res=1;
        while(n){
            if(n&1)
                res=(long long)res*base%m;
            base=(long long)base*base%m;
            n>>=1;
        }
        return res;
    }
    int countGoodNumbers(long long n) {
        return (long long)fastpow(5,(n+1)/2)*fastpow(4,n/2)%m;
    }
};